\section{Conclusion}
In this paper we prove a tight unconditional lower bound on the time complexity of distributed random walk computation, implying that the algorithm in \cite{DasSarmaNPT-PODC10} is time optimal. To the best of our knowledge, this is the first lower bound that the diameter plays a role of multiplicative factor. Our proof technique comes from strengthening the connection between communication complexity and distributed algorithm lower bounds initially studied in \cite{DasSarmaHKKNPPW10} by associating {\em rounds} in communication complexity to the distributed algorithm running time, with network diameter as a trade-off factor.
%Our technique can be of independent interest and may be useful in showing non-trivial lower bounds on the complexity of other fundamental distributed computing problems.

There are many open problems left for random walk computation. One interesting open problem is showing a lower bound of performing a long walk. We conjecture that the same lower bound of $\tilde\Omega(\sqrt{\ell D})$ holds for any $\ell=O(n)$. However, it is not clear whether this will hold for longer walks. For example, one can generate a {\em random spanning tree} by computing a walk of length equals the cover time (using the version where every node knows their positions) which is $O(mD)$ where $m$ is the number of edges in the network (see detail in \cite{DasSarmaNPT-PODC10}). It is interesting to see if performing such a walk can be done faster.  Additionally, the upper and lower bounds of the problem of generating a random spanning tree itself is very interesting since its current upper bound of $\tilde O(\sqrt{m}D)$~\cite{DasSarmaNPT-PODC10} simply follows as an application of random walk computation~\cite{DasSarmaNPT-PODC10} while no lower bound is known.
%
Another interesting open problem prove the lower bound of $\tilde \Omega(\sqrt{K\ell D})$ for some value of $\ell$ for the problem of performing {\em $K$ walks} of length $\ell$.



In light of the success in proving distributed algorithm lower bounds from communication complexity in this and the previous work~\cite{DasSarmaHKKNPPW10}, it is also interesting to explore further applications of this technique. One interesting approach is to show a connection between distributed algorithm lower bounds and other models of communication complexity, such as multiparty and asymmetric communication complexity (see, e.g., \cite{KNbook}).
%
One particular interesting research topic is applying this technique to distance-related problems such as shortest $s$-$t$ path, single-source distance computation, and all-pairs shortest path. The lower bound of $\Omega(\sqrt{n})$ are shown in \cite{DasSarmaHKKNPPW10} for these types of problems. It is interesting to see if there is an $O(\sqrt{n})$-time algorithm for these problems (or any sub-linear time algorithm) or a time lower bound of $\omega(\sqrt{n})$ exists. 
%
The special cases of these problems on complete graphs (as noted in \cite{Elkin-sigact04}) are particularly interesting. 
%
Besides these problems, there are still some gaps between upper and lower bounds of problems considered in \cite{DasSarmaHKKNPPW10} such as the minimum cut and generalized Steiner forest. 





